package union_find_Algorithm;

import 二分查找.easy.剑指Offer53I在排序数组中查找数字;

/**
 * 使用数组使用一个基本的并查集结构
 */

/**
 * 下面的算法虽然可以实现一个并查集，但是效率并不高，因为可以出现这样的情况：
 *      1 <-- 2 <-- 3 <-- 4 <-- 5......
 * 这样实际上对于搜索节点的根节点x而言是线性复杂度的，如果这个链比较长，那么搜索的效率就会比较低
 *
 * 所以我们考虑如何优化我们的算法?
 *      对于find方法而言，就是找到节点的根节点，所以没什么可以优化的，那么我们主要的优化对象就是
 *      union(x,y)方法，按照下面的第一次的写法，我们的做法是找当当前两个节点的根节点，然后直接将
 *      这两个节点连起立
 *
 * 1. 压缩路径法
 *      如果当前两个节点x，y要进行union，假设当前将x作为y的相对根节点即 x <--- y
 *      但是x的根节点未必是自己，所以递归找到x的根节点，然后重复，直到找到最终的根节点
 *      然后 root[y] = 最终找到的节点，写成代码就是：root[y] = find(x)
 *
 */
@SuppressWarnings("all")
public class UnionFind {
    private int maxsize; // 并查集的的最大容量
    private int[] root; // 并查集的容器 root[i]表示第i个节点的根节点

    public UnionFind(int maxsize) {
        this.maxsize = maxsize; // 初始化最大容量
        root = new int[this.maxsize]; // 初始化数组
        for (int i = 0; i < this.maxsize; i++) {
            root[i] = i; // 初始化时，每个节点以自己为根节点
        }
    }

    /**
     * 查找节点x的根节点
     * @param x
     * @return
     */
    public int find(int x) {
        if (root[x] == x) { // 如果当前节点x的节点为自己直接返回
            return root[x];
        }
        return find(root[x]); // 否则递归到x的跟节点 含义就是找到相对于x的根节点，然后接着递归x的跟节点
    }

    /**
     * 合并节点x和y(指的是合并x，y的根节点)
     * @param x
     * @param y
     */
    public void union1(int x, int y) {
        int rootX = this.find(x);
        int rootY = this.find(y);
        if (rootX != rootY) {
            root[rootY] = rootX;
        }
    }

    public static void main(String[] args) {

    }
}
